package com.jack.leetcode.array;

/***
 * 获取第K大的数
 * @author zhangjie
 * @date 2020/4/22 22:11
 */
public class 寻找两个有序数组的中位数4 {

    public static void main(String[] args) {
        int[] num1 = {1,3};
        int[] num2 = {2};
        System.out.println(findMedianSortedArrays(num1,num2));
    }

    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int left = (m + n + 1) / 2;
        int right = (m + n + 2) / 2;
        return (getKth(nums1, 0, m - 1, nums2, 0, n - 1, left)
                + getKth(nums1, 0, m - 1, nums2, 0, n - 1, right)) * 0.5;
    }

    private static int getKth(int[] num1, int start1, int end1, int[] num2, int start2, int end2, int k) {
        int len1 = end1 - start1 + 1;
        int len2 = end2 - start2 + 1;
        if (len1 > len2) {
            return getKth(num2, start2, end2, num1, start1, end1, k);
        }
        if (len1 == 0) {
            return num2[k + start2 - 1];
        }
        if (k == 1) {
            return Math.min(num1[start1], num2[start2]);
        }
        int i = start1 + Math.min(num1.length, k / 2) - 1;
        int j = start2 + Math.min(num2.length, k / 2) - 1;

        if (num1[i] > num2[j]) {
            return getKth(num1, start1, end1, num2, j + 1, end2, k - (j - start2 + 1));
        } else {
            return getKth(num1, i + 1, end1, num2, start2, end2, k - (i - start1 + 1));
        }
    }
}
